
from typing import List



class Solution:
    def maxProductPath(self, grid: List[List[int]]) -> int:
        m,n=len(grid),len(grid[0])
        mag=[[0]*n for _ in range(m)]
        mng=[[0]*n for _ in range(m)]
        mag[0][0]=mng[0][0]=grid[0][0]
        for i in range(1,n):
            mag[0][i]=mng[0][i]=mag[0][i-1]*grid[0][i]
        
        for i in range(1,m):
            mag[i][0]=mng[i][0]=mag[i-1][0]*grid[i][0]

        for i in range(1,m):
            for j in range(1,n):
                if grid[i][j] >=0:
                    mag[i][j]=max(mag[i][j-1],mag[i-1][j])*grid[i][j]
                    mng[i][j]=min(mng[i][j-1],mng[i-1][j])*grid[i][j]
                else:
                    mag[i][j]=min(mng[i][j-1],mng[i-1][j])*grid[i][j]
                    mng[i][j]=max(mag[i][j-1],mag[i-1][j])*grid[i][j]
        if mag[m-1][n-1]<0:
            return -1
        else:
            return mag[m-1][n-1]%(1e9+7)

if __name__=="__main__":
    s=Solution()
    v=[[ 1, 4,4,0],
             [-2, 0,0,1],
             [ 1,-1,1,1]]
    print(s.maxProductPath(v))